package LeetCode;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}17:24
 */
public class interview49 {
    public int nthUglyNumber(int n) {

        int dp[] = new int[n];
        dp[0] = 1;//因为1就是丑数
        for (int i = 1; i < n; i++){        int a = 0;
            int b = 0;
            int c = 0;
            int n1 = dp[a]*2;int n2 = dp[b]*3;int n3 = dp[c]*5;
            dp[i] = Math.min(Math.min(n1,n2),n3);
            if (dp[i] == n1)
                a++;
            if (dp[i] == n2)
                b++;
            if (dp[i] == n3)
                c++;
        }
        return dp[n-1];
    }
}
